using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    public class Quicksort
    {
        private int[] array;
        public Quicksort(int[] array)
        {
            this.array = array;
        }
        public void sort()
        {
            quickSort(array, 0, array.Length - 1);
        }
        public void print()
        {
            for (int i = 0; i < array.Length; i++)
            {
                Console.WriteLine(array[i]);
            }
        }

        private void quickSort(int[] src, int begin,int end)
        {
            if (begin < end) 
            {
                int key = src[begin];
                int i = begin;
                int j = end;
                while (i < j)
                {
                    while (i < j && src[j] > key)
                    {
                        j--;
                    }
                    if (i < j)
                    {
                        src[i] = src[j];
                        i++;
                    }
                    while (i < j && src[i] < key)
                    {
                        i++;
                    }
                    if (i < j)
                    {
                        src[j] = src[i];
                        j--;
                    }
                    src[i] = key;
                    quickSort(src, begin, i-1);
                    quickSort(src, i+1,end);
                }
            }
        }

    }
}
